The present invention relates to a tone dependent error diffusion halftoning method, and in particular to an efficient tone dependent error diffusion halftoning method with optimized thresholds and error weights that produce a high quality halftone image.
Continuous-tone images, such as charts, drawings, and pictures, may be represented as a two-dimensional matrix of picture elements (pixels). The spatial resolution and intensity level for each pixel are chosen to correspond to the particular output device used.
Digital halftoning is the process of transforming a continuous-tone image to a binary image, i.e., the pixel is either on or off. The low pass characteristic of the human visual system allows the binary texture patterns to be perceived as continuous-tones.
Hardcopy output devices, such as inkjet printers, are bi-level devices that eject droplets of ink to form dots on a medium. Such printers cannot print continuous-tone images and, thus, use digital halftoning so that the printed binary image on the medium will be perceived as the original image.
For printing applications, absorptance is used to represent a pixel value. A printing process typically puts absorptive dots on white paper. For an ideal device model, the colorant absorptance is 1 (a dot is printed); and the paper absorptance is 0 (no dot is printed). A pixel value in a general continuous-tone, i.e., gray scale, image is represented in units of absorptance between 0 and 1. It should be understood, of course, that the pixel value may be represented by a xe2x80x9cnear continuous-tonexe2x80x9d range, e.g., from 0 to 255, as is used in conventional computer monitors. The binary tone level in such a case will be represented as either 0 (off) or 255 (on).
Halftoning methods are described in the book Digital Halftoning, by Robert Ulichney, The MIT Press, 1987, incorporated herein by reference. Generally, halftoning methods can be grouped into three categories. They are iterative optimization methods, screening, and error diffusion.
Iterative methods use a human visual system model to minimize the perceived error between the continuous-tone image and the halftone image. An iterative method is direct binary search, which can be used to create high quality halftone images. Unfortunately, iterative methods require a great deal of computation which makes real time image processing impractical.
Screening, on the other hand, is a low complexity halftoning method that does not provide very high quality halftone images. A screen is defined by a matrix of threshold values. To binarize a continuous-tone image, the threshold matrix is periodically tiled over the image. Pixels that are greater than the corresponding matrix threshold values are binarized to 1; otherwise they are binarized to 0.
Error diffusion halftoning methods use a feedback loop to subtract the past weighted diffused errors from an input pixel value to obtain a modified pixel value. The modified pixel value is then compared with a threshold value to determine the halftone output value. Thus, the decision about whether or not to print a dot at a particular pixel is based not only on the continuous-tone level for that pixel, but on what has happened before for previously processed pixels. The error to be diffused, i.e., the quantizer error, is obtained by subtracting the modified pixel value from the output value. The error is then diffused to a set of future pixel locations by subtracting the weighted error from the future pixel locations. The local tone will be preserved if the sum of the weights is 1.
Error diffusion is an efficient halftoning method compared with direct binary search, but is more complex than screening. However, halftone images produced by conventional error diffusion methods are typically of lower quality than images produced by direct binary search methods.
A well known error diffusion technique is described by R. Floyd and L. Steinberg in the paper Adaptive Algorithm for Spatial Grey Scale, SID Int""l. Sym. Digest of Tech. Papers, pp. 36-37 (1975), incorporated herein by reference.
A diagram of the conventional error diffusion system 10 is shown in FIG. 1. As shown in FIG. 1, the input pixel value, which has continuous-tone value, is represented as f[m,n], where m and n are the pixel locations; the modified pixel value is represented by u[m,n]; and the output halftone value is represented by g[m,n], which is determined by a thresholding operation as follows:                               g          ⁡                      [                          m              ,              n                        ]                          =                  {                                                                      1                  ,                                                                                                                        if                      ⁢                                              xe2x80x83                                            ⁢                                              u                        ⁡                                                  [                                                      m                            ,                            n                                                    ]                                                                                      ≥                                          t                      ⁡                                              [                                                  m                          ,                          n                                                ]                                                                              ,                                                                                                      0                  ,                                                                              otherwise                  ,                                                                                        equ        .                  xe2x80x83                ⁢        1            
where t[m,n] is the threshold matrix 12.
The quantizer error d[m,n] is determined by subtracting the modified pixel value u[m,n] from the output halftone value g[m,n] at adder 14 as follows:
d[m, n]=g[m, n]xe2x88x92u[m, n].xe2x80x83xe2x80x83equ. 2
The quantizer error d[m,n] is then diffused to neighboring, subsequently processed pixel locations through the error-weighting matrix 16.
The modified pixel value u[m,n] is updated as:
u[m+k,n+1]←u[m+k,n+1]xe2x88x92w[k,l]d[m,n],xe2x80x83xe2x80x83equ. 3
where w[k,l] is the error-weighting matrix 16. To preserve the local tone,                                           ∑                          k              ,              l                                ⁢                      w            ⁡                          [                              k                ,                l                            ]                                      =        1                            equ        .                  xe2x80x83                ⁢        4            
Thus, the inputs to adder 18 may be represented as:                                                                         u                ⁡                                  [                                      m                    ,                    n                                    ]                                            =                              xe2x80x83                            ⁢                                                f                  ⁡                                      [                                          m                      ,                      n                                        ]                                                  -                                                      ∑                                          k                      ,                      l                                                        ⁢                                                            w                      ⁡                                              [                                                  k                          ,                          l                                                ]                                                              ⁢                                          d                      ⁡                                              [                                                                              m                            -                            k                                                    ,                                                      n                            -                            1                                                                          ]                                                                                                                                                                    =                              xe2x80x83                            ⁢                                                f                  ⁡                                      [                                          m                      ,                      n                                        ]                                                  -                                  c                  ⁡                                      [                                          m                      ,                      n                                        ]                                                                                                          equ        .                  xe2x80x83                ⁢        5            
were c[m,n] is the modification term defined by:                               c          ⁡                      [                          m              ,              n                        ]                          =                              ∑                          k              ,              l                                ⁢                                    w              ⁡                              [                                  k                  ,                  l                                ]                                      ⁢                                          d                ⁡                                  [                                                            m                      -                      k                                        ,                                          n                      -                      1                                                        ]                                            .                                                          equ        .                  xe2x80x83                ⁢        6            
Thus, the modification term c[m,n] is the diffused quantizer errors from previously processed pixels.
The conventional error diffusion system 10 binarizes an image in conventional raster scan order. The threshold t[m,n] in the threshold matrix 12 has a constant value, e.g., 0.5, for all m, n. The error weighting matrix 16 uses four non-zero weights w[0,1]=7/16, w[1,xe2x88x921]=3/16, w[1,0]=5/16, and w[1,1]=1/6 which are used to diffuse the error as shown in FIG. 2. FIG. 2 is a diagram 20 showing the distribution of the error, where the current pixel 22 being processed is indicated by a xe2x80x9cP.xe2x80x9d
The conventional error diffusion system 10 has long been known to produce smooth and sharp halftone images. FIG. 3 is a gray level halftoned image 30 generated using the conventional error diffusion system 10. The image 30 of FIG. 3 ranges from full black, i.e., a tone of 1, to full white, i.e., a tone of 0 (if using absorptance). As can be seen in FIG. 3, system 10 generates visible artifacts, such as worms 32, 33 in the highlight and shadow areas and structured patterns 34, 36, and 38 in the mid-tone areas.
Many error diffusion variations and enhancements have been developed to improve the halftone quality. For example, some error diffusion systems modify the thresholds by replacing the fixed threshold with an ordered threshold matrix or by using a matrix which has sparse threshold values along one of its diagonals, the direction of the diagonal being perpendicular to the prevailing direction of worm artifacts. One method described in J. Sullivan, R. Miller and G. Pios, xe2x80x9cImage Halftoning Using a Visual Model In Error Diffusion,xe2x80x9d J. Opt. Soc. Am. A, Vol. 10, No. 8, pp. 1714-1724, August 1993, which is incorporated herein by reference, determines the quantizer threshold with past outputs using a visual system model that is incorporated directly into the architecture of the error diffusion system. The architecture in the system described by Sullivan et al., is complex because of extra filters used for the visual system model, which requires additional computation.
Some error diffusion methods use variable error weights, including randomly dithering filter weights and using an LMS algorithm in adaptive signal processing to adjust the weights for minimizing an error criterion. Other methods of error diffusion, discussed in B. W. Kolpatzik and C. A. Bouman, xe2x80x9cOptimized Error Diffusion for Image Display,xe2x80x9d Journal of Electronic Imaging 1(3), 277-292, July 1992, and P. W. Wong and J. P. Allebach, xe2x80x9cOptimum Error Diffusion Kernel Design,xe2x80x9d Proceedings of SPIE/ISandT Symposium on Electronic Imaging, invited paper, San Jose, Calif., January 1997, both of which are incorporated by reference, use an optimum error-weighting design based on visual modeling. These methods, however, do not optimize the weight set in a tone-dependent manner.
Current error diffusion methods, however, require extensive processing and result in undesirable visual artifacts and/or a poor quality image relative to direct binary search halftoning.
What is needed is an efficient halftoning method that provides a high quality image.
An efficient haltoning system uses a tone dependent error diffusion halftoning method with tone dependent thresholds and error weightings that are optimized by minimizing a model based cost function. For each midtone level, a halftone image is generated by a direct binary search method and an error diffusion method. The magnitudes of the fast Fourier transforms of the halftone images are compared using a visual cost function and the thresholds and error weightings are altered to minimize the cost function. For highlight and shadow tone levels, the halftone image from the error diffusion system is compared to the continuous tone image after filtering the images via a human visual system model. Again by minimizing the cost function, the thresholds and error weightings are optimized. Once the threshold and error weightings are optimized, they may be maintained in a look-up table. Thus, a tone dependent error diffusion system in accordance with the present invention efficiently processes an image while producing high quality images. Because no additional filters are used on the error diffusion architecture, there is no additional computation required.
The tone dependent error diffusion halftoning method uses an upper and lower threshold to compare with the modified pixel value. If the modified pixel value is greater than the upper threshold, a dot is printed, if less than the lower threshold, no dot is printed, and if between, a binary bitmap is used to determine whether a dot should be printed.
Further, in an embodiment of the present invention for a conventional raster scan and a 2-row serpentine scan, the area that the error is diffused over is varied according to the input pixel value. Thus, if the input pixel value is at an extreme of the tone range, e.g., in the highlight or shadow tone levels, the error is diffused over a large area. If however, the input pixel value is in the midtone region, the error is diffused over a smaller area. A transitional tone region may be also be used, in which case the error is diffused over an area larger than the midtone diffused area but smaller than the highlight/shadow tone area. Further, if in a binary region where the input pixel value is either all on or all off, i.e., 1 or 0, the entire error may be diffused vertically or diagonally if a conventional raster scan is used.
To avoid start-up artifacts, the pixel values may be modified by adding random noise with variance equal to that of the average modification term.